The present invention is generally related to queuing systems for microprocessors and other environments. More specifically, an embodiment of the present invention includes a method for queuing and servicing requests that prevents the occurrence of live-lock conditions.
Computer processors maintain queues for various purposes. These queues are managed using a range of different strategies, depending on the queue""s intended uses. First-In-First-Out (FIFO) queues, for example, are used where queued items must be serviced in the order in which they are received. Find-First-One (FF1) queues are a slightly different example. FF1 queues are used where queue items may be served without regard to the order in which they arrive. The entity that services an FF1 queue is free to retrieve any queue item that is ready for service. Typically, this means that the servicing entity simply retrieves the first queue item that is located and is ready for service. This is true even if that item was just added to the queue.
For many applications, queues are maintained using fixed register sets. Thus, an exemplary queue might be maintained in a set of eight, ten or some other number of registers. In the typical case, each register has an associated valid bit. Each bit is turned on to indicate that its associated register contains a queue item that is ready for servicing. The servicing entity toggles these valid bits when it removes items from the queue.
A representative queue of this type is designated 100 in FIG. 1. Queuing system 100 includes a series of registers, of which registers 102a through 102e are representative. Each register 102 has an associated valid bit 104. For a typical FF1 strategy, register 102d would be the first register to be serviced in queuing system 100 (since it is the first register 102 having a set valid bit 104). The servicing entity would clear valid bit 104d to indicate the servicing of register 102d. Assuming no other changes to queuing system 100, register 102e would be the next register to be serviced.
FF1 queues provide a simple, effective and relatively inexpensive queuing strategy. FF1 queuing may be used wherever there is no absolute requirement that queued items be serviced in a particular order. Unfortunately, FF1 queuing can also lead to the creation of a condition known as live-locking where queued items may wait for extended or even indefinite periods for servicing.
Live-locking can be explained by reference to queuing system 100 of FIG. 1. As noted previously, queuing system 100 includes at least two registers (102d and 102e) that are ready for servicing. The FF1 strategy services register 102d first. It is possible that a new item will be added to the queue while register 102d is being serviced. This new item may be placed in any register 102 including now available register 102d. In fact, if new items arrive at a fast enough rate it is possible that register 102d (or a preceding register 102) will always be valid when the servicing entity inspects queuing system 100. If this is the case, the probability of selecting following registers 102 (such as register 102e) becomes diminished. In some cases, the repeated availability of preceding registers 102 will entirely prevent the servicing of subsequent registers 102. This is a live-lock condition.
The potential for live-lock conditions is a major drawback to existing FF1 queuing systems. Within these systems, it is possible for valid items to remain queued indefinitely. In most cases, this means that requested work is not getting done or service is being delayed.
Based on the foregoing, it may be appreciated that there is a need for methods that prevent live-lock conditions in queuing systems. This need is especially acute where FF1 and similar queuing strategies are employed.
An embodiment of the present invention provides a queuing system that avoids live-locking. A representative implementation of this system 1) selects a first queue item pointed to by a rotating pointer if the first queue item is ready to be serviced, 2) selects a second queue item pointed to by a find-first-pointer if the first queue item is not ready to be serviced, and 3) updates the rotating pointer so that the rotating pointer points to a third queue item.
Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description herein. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.